Shahar Dobzinski
Abstract:
We consider the problem of designing a revenue-maximizing auction for
a single item, when the values of the bidders are drawn from a
correlated distribution. We show that one can find in poly time a
deterministic revenue-maximizing auction that guarantees at least 3/5
of the revenue of the best truthful-in-expectation auction. The proof
consists of three steps:
(1) Showing that the optimal truthful-in-expectation auction for a
constant number of bidders can be computed in polynomial time.
(2) A "derandomization" algorithm that implements every 2-player
truthful-in-expectation mechanism as a universally truthful mechanism.
(3) An analysis of three new auctions that have complementary properties.
Joint work with Hu Fu and Bobby Kleinberg.